// Problem 178: Step numbers

// Consider the number 45656.
// It can be seen that each pair of consecutive digits of 45656 has a difference of one.
// A number for which every pair of consecutive digits has a difference of one is called a step number.
// A pandigital number contains every decimal digit from 0 to 9 at least once.
// How many pandigital step numbers less than 1040 are there?

package main

import "fmt"

var map178 map[int]int = make(map[int]int)

//var table178 [5][31]int

var table178 = [5][31]int{
	{1, 2, 4, 7, 13, 23, 43, 78, 148, 274, 525, 985, 1896, 3586, 6913, 13138, 25328, 48278, 93022, 177648, 342055, 654074, 1258561, 2408769, 4632273, 8871498, 17052673, 32674099, 62782246, 120338401, 231158566},
	{1, 3, 6, 12, 22, 42, 77, 147, 273, 524, 984, 1895, 3585, 6912, 13137, 25327, 48277, 93021, 177647, 342054, 654073, 1258560, 2408768, 4632272, 8871497, 17052672, 32674098, 62782245, 120338400, 231158565, 443195806},
	{1, 3, 7, 14, 28, 53, 103, 194, 375, 709, 1369, 2599, 5015, 9550, 18413, 35138, 67692, 129368, 249031, 476424, 916504, 1754693, 3373710, 6462727, 12420398, 23802599, 45729571, 87664300, 168376318, 322857404, 619983660},
	{1, 3, 7, 15, 30, 60, 116, 227, 435, 844, 1614, 3119, 5964, 11500, 22000, 42364, 81090, 156009, 298776, 574449, 1100619, 2115149, 4053958, 7788125, 14931101, 28676898, 54990201, 105594072, 202519003, 388825094, 745825184},
	{1, 3, 7, 15, 31, 62, 123, 240, 468, 904, 1749, 3364, 6484, 12449, 23950, 45951, 88316, 169407, 325417, 624194, 1198644, 2299264, 4414414, 8468373, 16256499, 31187601, 59864500, 114854702, 220448775, 422967779, 811792874},
}

func p178() {
	//load table178 by the following. Actually it's symmetrical.
	// for i := 0; i < 5; i++ {
	// 	for j := 0; j < 31; j++ {
	// 		table178[i][j] = stepNumberStartsWith(byte(48+i), j)
	// 	}
	// }
	ans := 0
	for _, x := range []byte("1234") {
		ans += 2 * generateMap(x, 0x3ff, 39)

	}
	ans += generateMap('9', 0x3ff, 39)
	fmt.Println("Problem 178:", ans)
}

func handle178(last byte, length, check int, count *int) {
	check &= ^(1 << (last - 48))
	if check == 0 {
		*count += table178[last-48][length]
	} else if length > 0 {
		if last < 57 {
			handle178(last+1, length-1, check, count)
		}
		if last > 48 {
			handle178(last-1, length-1, check, count)
		}
	}
}

// Start with `s` and the max length is `l+1`
func stepNumberStartsWith(s byte, l int) int {
	ans := 1
	if l > 0 {
		if s == 57 {
			ans += stepNumberStartsWith(s-1, l-1)
		} else if s == 48 {
			ans += stepNumberStartsWith(s+1, l-1)
		} else {
			ans += stepNumberStartsWith(s+1, l-1) + stepNumberStartsWith(s-1, l-1)
		}
	}
	return ans
}

// Start with `s` and the max length is `maxlen`
func generateMap(last byte, check, maxlen int) (ans int) {
	var key int = (check*100+int(last))*100 + maxlen
	if ans, ok := map178[key]; ok {
		return ans
	}
	i := last - 48
	check &= ^(1 << i)
	if check == 0 {
		if i > 4 {
			i = 9 - i
		}
		ans = table178[i][maxlen]
		return ans
	} else if maxlen > 0 {
		if last == 57 {
			ans = generateMap(last-1, check, maxlen-1)
		} else if last == 48 {
			ans = generateMap(last+1, check, maxlen-1)
		} else {
			ans = generateMap(last+1, check, maxlen-1) + generateMap(last-1, check, maxlen-1)
		}
	} else {
		ans = 0
	}
	map178[key] = ans
	return ans
}
